<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="libman.css">
<TITLE>
Edge-finder
</TITLE>
</HEAD>
<BODY >
<A HREF="libman023.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman021.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc53">4.3</A>&nbsp;&nbsp;Edge-finder</H2>
The libraries <B>ic_edge_finder</B> and <B>ic_edge_finder3</B>
implement stronger versions of the
disjunctive and cumulative scheduling constraints. They employ
a technique known as edge-finding to derive stronger bounds on
the starting times of the tasks.
The library is loaded using either
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
:- use_module(library(ic_edge_finder)).
</PRE></BLOCKQUOTE>
to get a weaker variant with quadratic complexity, or
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
:- use_module(library(ic_edge_finder3)).
</PRE></BLOCKQUOTE>
to get a stronger variant with cubic complexity.
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>disjunctive(+StartTimes,+Durations)</B><DD CLASS="dd-description"><BR>
<A NAME="@default154"></A>
A disjunctive scheduling constraint. StartTimes and Durations
are lists of equal length N of integer variables or integers.
The declarative meaning is that the N tasks with certain start times
and duration do not overlap at any point in time.<BR>
<BR>
<DT CLASS="dt-description"><B>cumulative(+StartTimes,+Durations,+Resources,++ResourceLimit)</B><DD CLASS="dd-description"><BR>
<A NAME="@default155"></A>
A cumulative scheduling constraint. StartTimes, Durations and Resources
are lists of equal length N of integer variables or integers.
ResourceLimit is an integer. The declarative meaning is:
If there are N tasks, each starting at a certain start time, having
a certain duration and consuming a certain (constant) amount of
resource, then the sum of resource usage of all the tasks does not
exceed ResourceLimit at any time.
This constraint can propagate more information than the implementation
in library(cumulative).<BR>
<BR>
<DT CLASS="dt-description"><B>cumulative(+StartTimes,+Durations,+Resources,+Area,++ResourceLimit)</B><DD CLASS="dd-description"><BR>
<A NAME="@default156"></A>
In this variant, an area (the product of duration and resource usage of
a task) can be specified, e.g. if duration or resource usage are not
known in advance. The edge-finder algorithm can make use of this information
to derive bound updates.
</DL>
<HR>
<A HREF="libman023.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman021.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
</BODY>
</HTML>
